public class Test6 {
    public static void main(String[] args) {
        int[][] grid = {{0,6,0}, {5,8,7},{0,9,0}};
        getMaximumGold(grid);
    }

    static boolean[][] check;
    static int m,n;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int sum = 0;
    public static  int getMaximumGold(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        check = new boolean[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(grid[i][j] != 0) {
                    check[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    check[i][j] = false;
                }
            }
        }
        return sum;
    }
    public static void dfs(int[][] grid, int i, int j, int path) {
        sum = Math.max(sum, path);

        for(int a = 0; a < 4; a++) {
            int x = i + dx[a];
            int y = j + dy[a];
            if(x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && grid[x][y] != 0) {
                // path += grid[x][y];
                check[x][y] = true;
                dfs(grid, x, y, path + grid[x][y]);
                // path -= grid[x][y];
                check[x][y] = false;
            }
        }
    }
}
